package algorithm.leetcode;

import java.util.BitSet;

/**
 * 给定一个字符串，找出不含有重复字符的最长子串的长度。
 * <p>
 * 示例：
 * <p>
 * 给定 "abcabcbb" ，没有重复字符的最长子串是 "abc" ，那么长度就是3。
 * <p>
 * 给定 "bbbbb" ，最长的子串就是 "b" ，长度是1。
 * <p>
 * 给定 "pwwkew" ，最长子串是 "wke" ，长度是3。请注意答案必须是一个子串，"pwke" 是 子序列  而不是子串。
 *
 * @author: zhouj-j
 * @since: 2018/7/3
 */
public class __003_length_of_longest_substring {

    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        BitSet set = new BitSet(128);
        int ans = 0, i = 0, j = 0;
        while (i < n && j < n) {
            if (!set.get(s.charAt(j))) {
                set.set(s.charAt(j++));
                ans = Math.max(ans, j - i);
            } else {
                set.clear(s.charAt(i++));
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new __003_length_of_longest_substring().lengthOfLongestSubstring("pwwkew"));
    }
}
